class code4 {
    //记忆化搜索
    public Set<String> hash;
    public int[] memo;//记忆化，保存每次计算的以startIndex起始的计算结果
    public boolean wordBreak(String s, List<String> wordDict) {
        memo = new int[s.length()];
        hash = new HashSet<>(wordDict);
        return dfs(s,0);
    }

    public boolean dfs(String s,int startIndex) {
        //出口
        if(startIndex == s.length()) {
            return true;
        }
        if (memo[startIndex] == -1) {
            return false;
        }
        for(int i=startIndex;i<s.length();i++) {
            String sub = s.substring(startIndex,i+1);

            //[sta,i]匹配
            //没匹配上
            if(!hash.contains(sub)) continue;
            //匹配上了
            boolean res = dfs(s, i + 1);
            if (res) return true;;
        }
        //找遍了startIndex~s.length()也没能完全匹配，标记从startIndex开始不能找到
        memo[startIndex] = -1;
        return false;
    }
}